package com.shm.leetcode;

/**
 * 1716. 计算力扣银行的钱
 * Hercy 想要为购买第一辆车存钱。他 每天 都往力扣银行里存钱。
 * <p>
 * 最开始，他在周一的时候存入 1 块钱。从周二到周日，他每天都比前一天多存入 1 块钱。在接下来每一个周一，他都会比 前一个周一 多存入 1 块钱。
 * <p>
 * 给你 n ，请你返回在第 n 天结束的时候他在力扣银行总共存了多少块钱。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 4
 * 输出：10
 * 解释：第 4 天后，总额为 1 + 2 + 3 + 4 = 10 。
 * 示例 2：
 * <p>
 * 输入：n = 10
 * 输出：37
 * 解释：第 10 天后，总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37 。注意到第二个星期一，Hercy 存入 2 块钱。
 * 示例 3：
 * <p>
 * 输入：n = 20
 * 输出：96
 * 解释：第 20 天后，总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96 。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= n <= 1000
 *
 * @author SHM
 */
public class TotalMoney {
    /**
     * 模拟
     * 根据题意进行模拟即可，分两步进行计算。
     * <p>
     * 先计算完整周：共 a = \left \lfloor \frac{n}{7} \right \rfloora=⌊
     * 7
     * n
     * ​
     * ⌋ 周，第一周起始日金额为 11，每周的起始日的金额递增 11，周内金额可使用「等差数列求和」公式直接求解。
     * <p>
     * 然后再计算最后一周（若有）的金额：共 b = n \pmod 7b=n(mod7) 天，使用紧接的起始日金额继续进行累加即可。
     * <p>
     * 时间复杂度：O(a + b)O(a+b)
     * <p>
     * 空间复杂度：O(1)O(1)
     * 作者：AC_OIer
     * 链接：https://leetcode-cn.com/problems/calculate-money-in-leetcode-bank/solution/gong-shui-san-xie-jian-dan-mo-ni-ti-by-a-ifit/
     *
     * @param n
     * @return
     */
    public int totalMoney(int n) {
        int sum = 0, k = 1;
        int week = n / 7;
        int day = n % 7;
        while (week-- > 0) {
            sum += (k + (k + 6)) * 7 / 2;
            k++;
        }
        while (day-- > 0) {
            sum += k++;
        }
        return sum;
    }

    /**
     * （优化）模拟
     * 更近一步，每个完整周的起始日金额相比上周起始日金额多 11，同时周内每日金额递增 11，因此相邻完整周的金额之和也满足「等差」性质，可直接使用「等差数列求和」公式 O(1)O(1) 求解完整周部分的金额之和；周后一周（若有）的金额也是同理。
     * <p>
     * 时间复杂度：O(1)O(1)
     * <p>
     * 空间复杂度：O(1)O(1)
     * 作者：AC_OIer
     * 链接：https://leetcode-cn.com/problems/calculate-money-in-leetcode-bank/solution/gong-shui-san-xie-jian-dan-mo-ni-ti-by-a-ifit/
     *
     * @param n
     * @return
     */
    public int totalMoney_1(int n) {
        int week = n / 7;
        int day = n % 7;
        int a1 = (1 + 7) * 7 / 2, an = (week + (week + 6)) * 7 / 2;
        int s1 = (a1 + an) * week / 2;
        week++;
        int s2 = (week + (week + day - 1)) * day / 2;
        return s1 + s2;
    }

    /**
     * 方法一：暴力计算
     * 记当前的天数是第 \textit{week}week 周的第 \textit{day}day 天。我们从第一周的星期一开始存钱，记 \textit{week} = 1week=1，\textit{day} = 1day=1。一周内，每一天比前一天多存 11 块钱。而每个周一，会比前一个周一多存 11 块钱。因此，每天存的钱等于 \textit{week} + \textit{day} - 1week+day−1。把每天存的钱相加就可以得到答案。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)。需要遍历一次 nn 得到答案。
     *
     * 空间复杂度：O(1)O(1)。只需要用到常数空间。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/calculate-money-in-leetcode-bank/solution/ji-suan-li-kou-yin-xing-de-qian-by-leetc-xogx/
     * @param n
     * @return
     */
    public int totalMoney_2(int n) {
        int week = 1, day = 1;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += week + day - 1;
            ++day;
            if (day == 8) {
                day = 1;
                week++;
            }
        }
        return sum;
    }

    /**
     * 方法二：等差数列求和进行优化
     * 因为每周七天存的钱之和比上一周多 77 块，因此每周存的钱之和的序列是一个等差数列，我们可以用等差数列求和公式来求出所有完整的周存的钱总和。剩下的天数里，每天存的钱也是一个等差数列，可以用相同的公式进行求和。最后把两者相加可以得到答案。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(1)O(1)。只需要用到常数时间。
     *
     * 空间复杂度：O(1)O(1)。只需要用到常数空间。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/calculate-money-in-leetcode-bank/solution/ji-suan-li-kou-yin-xing-de-qian-by-leetc-xogx/
     * @param n
     * @return
     */
    public int totalMoney_3(int n) {
        int week = n / 7;
        int firstWeek = (1+7)*7/2;
        int lastWeek = firstWeek+(week-1)*7;
        int weekMoney = (firstWeek+lastWeek)*week/2;

        int day = n % 7;
        int firstDay = week+1;
        int lastDay = firstDay+day-1;
        int dayMoney = (firstDay+lastDay)*day/2;
        return weekMoney+dayMoney;
    }

}
